import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    static class TreeNode{
        private char val;
        private TreeNode left;
        private TreeNode right;

        private TreeNode(char val){
            this.val = val;
        }
    }

    public TreeNode createTreeNode(){
        TreeNode node1 = new TreeNode('A');
        TreeNode node2 = new TreeNode('B');
        TreeNode node3 = new TreeNode('C');
        TreeNode node4 = new TreeNode('D');
        TreeNode node5 = new TreeNode('E');
        TreeNode node6 = new TreeNode('F');

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node4.right = node5;
        node3.left = node6;

        return node1;
    }

    public void postOrder1(TreeNode root){
        if (root == null){
            return;
        }
        postOrder1(root.left);

        postOrder1(root.right);
        System.out.print(root.val + " ");
    }

    List<Character> ret = new ArrayList<>();
    public List<Character> postOrder2(TreeNode root){
        if (root == null){
            return ret;
        }

        postOrder2(root.left);
        postOrder2(root.right);
        ret.add(root.val);

        return ret;
    }

    public List<Character> postOrder(TreeNode root){
        List<Character> ret = new ArrayList<>();
        if (root == null){
            return ret;
        }

        List<Character> leftTree = postOrder(root.left);
        ret.addAll(leftTree);


        List<Character> rightTree = postOrder(root.right);
        ret.addAll(rightTree);
        ret.add(root.val);
        return ret;

    }

    private int size = 0;
    public int treeSize1(TreeNode root){
        if (root == null){
            return 0;
        }

        size++;
        treeSize1(root.left);
        treeSize1(root.right);

        return size;
    }

    public int treeSize(TreeNode root){
        if (root == null){
            return 0;
        }

        return treeSize(root.left) + treeSize(root.right) + 1;
    }

    private int leafUseSize = 0;
    public void leafSize1(TreeNode root){
        if (root == null){
            return;
        }

        if (root.left == null && root.right == null){
            leafUseSize++;
        }

        leafSize1(root.left);
        leafSize1(root.right);
    }

    public int leafSize(TreeNode root){
        if (root == null){
            return 0;
        }

        if (root.left == null && root.right == null){
            return 1;
        }

        return leafSize(root.left) + leafSize(root.right);
    }
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTreeNode();
//        System.out.println(binaryTree.postOrder(root));
//        System.out.println(binaryTree.treeSize(root));
        System.out.println(binaryTree.leafSize(root));
        //System.out.println(binaryTree.leafUseSize);
    }
}
